package leetcode.d_1_99;

import java.util.*;

public class P40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new LinkedList<>();
        // 排序方便进行剪枝
        Arrays.sort(candidates);
        dfs(res,path,candidates,0,target);
        return res;
    }

    private void dfs(List<List<Integer>> res,Deque<Integer> path,int[] nums,int index,int target){
        if (target==0){
            res.add(new ArrayList<>(path));
            return;
        }
        if (index>=nums.length) return;
        List<Integer> pre=new ArrayList<>(nums.length);
        // 此处遍历决定的是每一个位置的数字的值
        for (int i=index;i<nums.length;i++){
            if (pre.contains(nums[i])) continue;
            // 剪枝
            if (target-nums[i]<0) break;
            path.addLast(nums[i]);
            pre.add(nums[i]);
            dfs(res,path,nums,i+1,target-nums[i]);
            path.removeLast();
        }
    }
}
